出典: フリー百科事典『ウィキペディア(Wikipedia)』
| この記事のほとんどまたは全てが唯一の出典にのみ基づいています。 他の出典の追加も行い、記事の正確性・中立性・信頼性の向上にご協力ください。 出典検索?: "カルーシュ・クーン・タッカー条件" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL(2013年10月) |
カルーシュ・クーン・タッカー条件(英: Karush-Kuhn-Tucker condition)あるいはKKT条件とは、非線形計画において一階導関数が満たすべき最適条件を指す。ラグランジュの未定乗数法が等式制約のみを扱うのに対して、KKT条件を用いた解法は不等式制約も扱うことができる。KKT条件に対応する連立方程式は、解析的に閉形式解法が導かれる特殊な場合を除いては直接的には解かない。すでにKKT条件の連立方程式を数値的に解く方法は数多く確立されており、それらを用いて解くのが一般的である。KKT条件は線形計画法における主双対内点法などの解法において、重要な役割を持つ。
対象となる非線形計画問題[編集]
次のような非線形計画問題を考える。
![{\displaystyle {\text{Minimize}}\;f(x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4213d233e691c9215c9a3f232fcbd6a6b684e977)
![{\displaystyle {\text{subject to}}\;g_{i}(x)\leq 0,\;h_{j}(x)=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e41e2c1ab3ab8cb1cd64b907243c8be70cd2daf7)
このとき、x が変数、f が目的関数、gi (i = 1, 2, ... , m) は不等式制約を表す関数、hj (j = 1, 2, ... , l) は等式制約を表す関数である。不等式制約と等式制約の数はそれぞれ m および l で表す。
この際、KKT条件が局所値の必要条件となるためには、正規条件と呼ばれるいくつかの条件のうちの1つを満たす必要がある。一例として、f が凸関数で、かつ gi および hj がアフィン関数であるなどの条件がある.
必要条件[編集]
目的関数
と制約の関数
が
において連続かつ微分可能であるとする。もし
が目的関数の極小値を与えるのなら、KKT乗数と呼ばれる
で以下を満たすものが存在する。
- 停留性
- For maximizing f(x):
![{\displaystyle \nabla f(x^{*})=\sum _{i=1}^{m}\mu _{i}\nabla g_{i}(x^{*})+\sum _{j=1}^{l}\lambda _{j}\nabla h_{j}(x^{*}),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6cd1b48c69b683c3bc4feafe555c8d9340d649e5)
- For minimizing f(x):
![{\displaystyle -\nabla f(x^{*})=\sum _{i=1}^{m}\mu _{i}\nabla g_{i}(x^{*})+\sum _{j=1}^{l}\lambda _{j}\nabla h_{j}(x^{*}),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b36c17ecaee0cc2cc3c245eb0ef464eb33e34163)
- 主問題の実行可能条件
![{\displaystyle g_{i}(x^{*})\leq 0,{\mbox{ for all }}i=1,\ldots ,m}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2c6c02ce74882eb423fbe96ba1dd59308386f34c)
![{\displaystyle h_{j}(x^{*})=0,{\mbox{ for all }}j=1,\ldots ,l\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/465273bc83ce619e88128e080951ddcb8a968ca9)
- 双対問題の実行可能条件
![{\displaystyle \mu _{i}\geq 0,{\mbox{ for all }}i=1,\ldots ,m}](https://wikimedia.org/api/rest_v1/media/math/render/svg/16e9483c9de1f21ee80cdb995c483da59753a71d)
- スラック変数に関する条件
![{\displaystyle \mu _{i}g_{i}(x^{*})=0,{\mbox{for all}}\;i=1,\ldots ,m.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0ff7efd8dab422fff779593939121197247fcdfd)
特に m = 0 の場合は等式制約のみを持つ問題となるので、KKT条件はラグランジュの未定乗数が満たすべき条件と同値になり、KKT乗数はラグランジュ乗数と呼ばれる。仮に、いくつかの関数が微分不可能である場合、劣微分を用いたKKT条件を同様に定めることができる。
関連項目[編集]
参考文献[編集]